php实现variable-precision SWAR算法

发表于

在看 <<redis的设计与实现>> 时遇到一个问题，如何统计一个二进制串中 1 出现的次数。 书上一个介绍了三种方法：循环检查，查表统计以及 swar 算法。

首先看看 swar 算法的实现：

1
2
3
4
5
6
$int = ($int & 0x55555555) + (($int >> 1) & 0x55555555);
$int = ($int & 0x33333333) + (($int >> 2) & 0x33333333);
$int = ($int & 0x0f0f0f0f) + (($int >> 4) & 0x0f0f0f0f);
$int = ($int * 0x01010101) >> 24;

return $int & 0xff;

再简单介绍一下 swar 算法的原理。对任意一个长度为2的二进制数 x ，公式 x & 0b01 + (x >> 1) & 0b01 的结果，就是 x 中包含的 1 的个数，具体情况如下表:

x x & 0b01 + (x >> 1) & 0b01 结果
0b00 0b00 0
0b01 0b01 1
0b10 0b01 1
0b11 0b10 2

那么对于长度大于 2 的值呢？可以将数值进行两两分组，看作多个长度为 2 的二进制串的组合，然后对每一组运用上述公式进行计算，也就是算法实现的第一行。

通过第一行的计算后，原数值的两位一组的包含 1 个数的结果，保存在计算结果中，剩下的工作，就是对第一行的计算结果，两两分组后，进行求和。以十进制数为例，对 123 的各位数求和，公式为 3 + 20 /10 + 100 / 100。而对一个 4 位的二进制串 y，计算前两位与后两位的和公式为: y & 0b0011 + (y >> 2) & 0b0011，得到的 4 位二进制串表示的数，就是其结果，也就是算法实现的第二行。以次类推4位、8位、16位分组的求和，即可得到最终结果。

算法实现的第三行，就是计算按4位分组的和数，得到的结果是8位的结果组合。如果继续按8位分组算和的化，表达式应该是 $int = ($int & 0x00ff00ff) + (($int >> 8) & 0x00ff00ff)，但算法实现的第四行却并不是这样，为什么呢？因为表达式 $int * 0x01010101 计算的结果的第25到32位，实际上就是原值 $int 的 1到8位，9到16位，17到24位，25到32位 四个分组的数值和，这个结论写一下竖式乘法就可以验证。所以，按八位分组的和通过一个算式求和到第25到32位，然后右移24位到低位即可。

最后对结果进行 $int & 0xff 运算就可以得到最后的结果。因为在 php 中，整型数值溢出后会自动转化为浮点表示，如果第四行的乘法结果超出整形的表示返回，或者 php 是64位的版本，总之就是乘积的结果表示超过了32位，那么右移24位后的结果依然超出8位，所以还要对第四行的结果取低八位，得到最终的结果。